package algorithm;

import javax.validation.constraints.NotNull;
import java.util.Arrays;

/**
 * @Auther: ssk
 * @Date: 2019/1/23 18:13
 * @Description: 参考 https://www.cnblogs.com/answeryi/archive/2011/10/12/2209058.html
 *
 * 1 全排列 字典排序找后继
 *  对于全排列每一个数都有唯一后继,我们可以找每个数的后继,但如何找后继
 *  是否有后继很好判断，唯一没有后继的只有654321,它的特点是每位的数字比后面的大！
 *  如何找到后继，思路很清楚，即对于一个数，找到一个比它大的、最小的数！
 *  比如 1 2 5 4 3 它先找最后一个峰值,就是5,然后在最后一个峰值后找一个最后一个比峰值前面那个数大的最小的数,那就是3
 *  交换这两个数 1 3 5 4 2 然后把最后一个峰值到最后的数颠倒一下 1 3 2 4 5 就是 1 2 5 4 3 的后继
 *  如何判断没有后继 这个更容易 5 4 3 2 1 这样的就是最后一个没有后继,就是变成递减的了
 */
public class Next_permutation<T extends Comparable> {
    private T[] element;
    private int len ;
    private boolean frist;
    public Next_permutation(@NotNull  T[] element) {
        len = element.length;
        this.element = Arrays.copyOf(element,len);
        frist = false;
    }
    public void InitSort() {
        Arrays.sort(element);
    }

    /**
     *
     * @return 是否有后继
     */
    public boolean hasNext() {
        for (int i = 1; i < len; i++) {
            if (element[i].compareTo(element[i-1])>0) {
                return true;
            }
        }
        return false;
    }

    /**
     *
     * @return 下一个全排列
     */
    public T[] next(){
        if (!frist) {
            frist = true;
            return element;
        }
        int maxn=0 ,minn=0;
        T temp;

        // 找峰值
        for (int i = len-1; i > 0; i--) {
            if (element[i].compareTo(element[i-1])>0){
                maxn = i;
                break;
            }
        }
        temp = element[maxn-1];
        minn = len-1;
        // 寻找一个比峰值前面那个数temp大的最小数
        //数组全排列一直维持着峰值后面是递减的
        for (int i = maxn; i < len; i++) {
            if (temp.compareTo(element[i])>0){
                minn = i-1;
                break;
            }
        }
        temp = element[minn];
        element[minn]=element[maxn-1];
        element[maxn-1]=temp;
        // 颠倒
        for (int i = 0; i <(len - maxn)/2 ; i++) {
            temp = element[len-i-1];
            element[len-i-1]=element[i+maxn];
            element[i+maxn]=temp;
        }
        return element;
    }
    public static void main(String[] args) {
        Integer a[] ={1,2,3,4};
        Next_permutation<Integer> next_permutation = new Next_permutation<Integer>(a);
        next_permutation.InitSort();
        while (next_permutation.hasNext()){
            Integer temp[] = next_permutation.next();
            for (int i:temp) {
                System.out.print(i+" ");
            }
            System.out.println();
        }

        char ts[] ="acccc".toCharArray();
        Character s[] = new Character[ts.length];
        for (int i = 0; i < ts.length; i++) {
            s[i] =ts[i];
        }
        Next_permutation<Character> next_permutation1 = new Next_permutation<Character>(s);
        next_permutation.InitSort();
        while (next_permutation1.hasNext()){
            Character temp[] = next_permutation1.next();
            for (char i:temp) {
                System.out.print(i+" ");
            }
            System.out.println();
        }

    }
}
